/**********************************************************************
**	Authors: Erik Sapir & Lior Zibi

**
** Lazy list implementation: lock-free contains method.
** removed element are first removed logically and only than physically
**
**
**********************************************************************/

#ifndef __LAZY_LIST__H
#define __LAZY_LIST__H

#include "framework/cpp_framework.h"

using namespace CMDR;

template<typename T>
class LazyList : public set<T> {
private:
	//list node
	class Node : public HazardMemory::Object {
	public:
		const T m_item; //item stored in node
		AtomicMarkableReference<Node>	m_next; //next Node in list
		CMDR::ReentrantLock	m_lock; //Synchronizes Node.

		Node(const T& item) : m_item(item), m_next(null, false) { }
		Node(const T& item, Node* const next) : m_item(item), m_next(next, false) { }

		virtual ~Node() {;}

		virtual bool isValid() { 
			return (false == m_next.isMarked());
		}

		virtual HazardMemory::Object* getNextValid(const int indx) {
			return m_next.getReference();
		}

		virtual HazardMemory::Object* getNextValid(const int indx, int& stamp) {
			bool tmpStamp;
			HazardMemory::Object* tmpPtr = m_next.get(&tmpStamp);
			if(tmpStamp) stamp = 1; else stamp=0;
			return tmpPtr;
		}

		//lock node
		void Lock()  { m_lock.lock(); }

		//unlock node 
		void UnLock() { m_lock.unlock(); }
	};

private:
	VolatileType<Node*>	m_head; // First list Node
	SnapshotCounter		m_counter; //counter for number of element in the list

public:

	LazyList(int numOfThreads) : m_counter(numOfThreads) {
		printf("\n\tSet Is: Lazy List\n");

		// Add sentinels to start and end
		Node* tail = new Node(Integer::MAX_VALUE, null);
		m_head = new Node (Integer::MIN_VALUE, tail);
	}
 
	//desctructor - removes all list elements
	~LazyList() {
		//we assume no one access the object at this point.
		Node* pCurr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != pCurr) {
			next = pCurr->m_next.getReference();
			delete pCurr;
			pCurr = next;
		}
	}
	
	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;
	
		while (true) {
			pPred = m_head;
			pCurr.extractNext(pPred, 0);

			//search for first element equal or greater than the new element
			while (pCurr->m_item < item) {
				pPred = pCurr;
				pCurr.extractNext(pPred, 0);
			}

			pPred->Lock(); 
			pCurr->Lock();

			//validate theat pred and curr are not deleted and
			//that pred.next = curr
			if (validate(pPred, pCurr)) {
				if (pCurr->m_item == item) {
					// element is already in list - nothing to add
					pCurr->UnLock();
					pPred->UnLock();
					return false;
				} else {
					// add new element to list
					std::auto_ptr<Node> newNode(new Node(item, pCurr.getReference()));
					pPred->m_next.set(newNode.get(), false);
					newNode.release();

					//element added successfully - increment number of element in list
					m_counter.inc(threadID);
					pCurr->UnLock();
					pPred->UnLock();

					return true;
				}
			}

			//always unlockj;
			pCurr->UnLock();
			pPred->UnLock();
		} 
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;

		while (true) {
			pPred = m_head;
			pCurr.extractNext(pPred, 0);

			//search for first element equal or greater than element to be removed 
			while (pCurr->m_item < item) {
				pPred = pCurr;
				pCurr.extractNext(pPred, 0);
			}

			pPred->Lock(); 
			pCurr->Lock();
			if (validate(pPred, pCurr)) {
				if (pCurr->m_item != item) {
					// element was not found in list - nothing to remove

					//always unlock
					pCurr->UnLock();
					pPred->UnLock();

					return false;
				} else {
					//element was found in list - first logically remove, than 
					//physically remove
					pCurr->m_next.set(pCurr->m_next.getReference(), true); //logically remove
					pPred->m_next.set(pCurr->m_next.getReference(), false); //physically remove
					
					//retire node - will be acctually deleted when not used anymore
					pCurr.retire();	

					//element removed successfully - decrement number of elements in list
					m_counter.dec(threadID);

					//always unlock
					pCurr->UnLock();
					pPred->UnLock();

					return true;
				}
			}

			//always unlock
			pCurr->UnLock();
			pPred->UnLock();
		} 
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pPred;
		HazardMemory::Ptr<Node> pCurr;
		pPred = m_head;
		pCurr.extractNext(pPred, 0);

		//search for first element equal or greater than element we are searching
		while (pCurr->m_item < item) {
			pPred = pCurr;
			pCurr.extractNext(pPred, 0);
		}

		//return true iff found element in list and it is not logically removed
		return (pCurr->m_item == item && pCurr->isValid());
	}


	void clean(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> pCurr;
		HazardMemory::Ptr<Node> pSucc;
		head = m_head;
		head->Lock();
		pCurr.extractNext(head, 0);

		//go over each and every element in list and remove it.
		while(pCurr->m_item < Integer::MAX_VALUE) {
			pCurr->Lock();

			pSucc.extractNext(pCurr,0);

			pCurr->m_next.set(pSucc.getReference(), true); //logically remove
			head->m_next.set(pSucc.getReference(), false); //physically remove

			//retire node - will be acctually deleted when not used anymore
			pCurr.retire();	

			//element removed successfully - decrement number of elements in list
			m_counter.dec(threadID);

			//always unlock
			pCurr->UnLock();

			pCurr.extractNext(head, 0);
		}

		//always unlock
		head->UnLock();
	}
	
	bool isEmpty(int threadID) {
		HazardMemory::Ptr<Node> pCurr;
		HazardMemory::Ptr<Node> pSucc;

		pCurr = m_head;

		//search an element that exist in the list, both logically and physically
		while (pCurr->m_item < Integer::MAX_VALUE) {
			//make sure element was not removed logically
			if (!pCurr->isValid())
				return false;

			pSucc.extractNext(pCurr, 0);
			pCurr = pSucc;
		}

		return true;
	}
	int size(int threadID){
		return m_counter.scan();
	}

private:
	//Check that prev and curr are still in list and adjacent
	bool validate(HazardMemory::Ptr<Node>& pPred, HazardMemory::Ptr<Node>& pCurr) {
		//assume both "pPred" & "pCurr" locked and can not change during this test
		if (pPred->isValid() && pCurr->isValid() && pPred->m_next.getReference() == pCurr.getReference())
			return true;
		else
			return false;
	}
}; 

#endif // __LAZY_LIST__H
